Luogu P2900 土地征用 斜率优化dp 题解

Posted on | In |
Words count in article: 758 | Reading time ≈ 3

一道裸的斜率优化dp

首先对于i,j，若存在a[i].len(以下简写为l[i])>=a[j].len&&a[i].wid(以下简写为w[i])>=a[j].wid,则j这块土地是无用的，在预处理时应去掉这些无用的土地。同时在预处理时可以将数据按l降序排列，同时产生的结果是w必然按升序排列（有兴趣的dalao可以自己证明），这样可方便后面的过程。

然后就是对着数据手推状转方程了（建议先自己推一遍），可知假设用f[i]表示前i块土地的最小价值，则有f[i]=min{f[j]+l[j+1]w[i]}。

然后对数据化简可知假设j比k优，则有f[j]+l[j+1]w[i]<f[k]+l[k+1]w[i],然后就可以得到(f[k]-f[j])/(l[j+1]-l[k+1])>w[i]

接着就是一个数形结合的思想了

一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。——周源

有兴趣的dalao可以阅读浅谈数形结合思想在信息学竞赛中的应用

总之这里将关系式抽象为形如y=kx+b的式子，只要维护组成图形的下凸性就行了，要弹出队尾的情况中节点的插入破坏了图形的下凸性

这里就要用到单调队列了，维护队列中的元素单调（然而我不会，所以请各位懂的大神指点

不多说见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define N 50010
using namespace std;
long long n,tot,q[N],head=1,tail=1,f[N];
struct node
{
    long long len,wid;
};struct node a[N];
struct node1
{
    long long lent,wide;
};struct node1 b[N];
bool mmp(node xx,node yy)
{
    return xx.len>yy.len||(xx.len==yy.len&&xx.wid>yy.wid);
}
double slope(int x,int y)
{
    return (double)(f[y]-f[x])/(double)(b[x+1].lent-b[y+1].lent);
}//slope 斜率，来自金山词霸
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].len,&a[i].wid);
    sort(a+1,a+1+n,mmp);
    for(int i=1;i<=n;i++)
        if(a[i].wid>b[tot].wide)//注意！一定要这样维护b中w的升序排列
        {
            b[++tot].lent=a[i].len;
            b[tot].wide=a[i].wid;
        }
    for(int i=1;i<=tot;i++)//1~tot动规
    {
        while(head<tail&&slope(q[head],q[head+1])<=b[i].wide)
            head++;//如果队首不是最优，就弹出队首
        f[i]=f[q[head]]+b[i].wide*b[q[head]+1].lent;
        while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i))
            tail--;//维护一个下凸包
        q[++tail]=i;//进队
    }
    printf("%lld\n",f[tot]);//这里也要用tot
    return 0;
}

望各位dalao谅解QWQ

[注] 图片、引文来源[模板] 斜率优化Dp详解

0%